

package graph

import "fmt";
import "container/vector";
import "sort";



const INF int64 = 9223372036854775807;

type Color int;

const (
    WHITE = Color(0);
    GREY = Color(1);
    BLACK = Color(2);
)


type Vertex interface {
    
}




type Edge struct {
    source Vertex;
    dest Vertex;
    weight int64;
}


func (e *Edge) String() string {
    return fmt.Sprintf("%s-> %s : %d", e.source, e.dest, e.weight);
}


func (e *Edge) Source() (Vertex) {
    return e.source;
}

func (e *Edge) Dest() Vertex {
    return e.dest;
}


func (e *Edge) Weight() (int64) {
    return e.weight;
}

func (e *Edge) Less(y interface{}) bool {
    return e.weight < y.(*Edge).weight;
}



// EdgeIter implements EdgeIterator
type EdgeIter struct {
    edges *vector.Vector;
    i int;
}

func (iter *EdgeIter) End() bool {
    return iter.i >= iter.edges.Len() - 1;
}

func (iter *EdgeIter) Next() (WeightedEdge) {
    iter.i++;
    return iter.Current();
}

func (iter *EdgeIter) Current() (WeightedEdge) {
    edge := iter.edges.At(iter.i).(*Edge); 
    return edge;
}




// VertexIter implements VertexIterator
type VertexIter struct {
    vertices *[]Vertex;
    i int;
}

func (iter *VertexIter) End() bool {
    return iter.i >= len(*iter.vertices) - 1;
}

func (iter *VertexIter) Next() (Vertex) {
    iter.i++;
    return iter.Current();
}

func (iter *VertexIter) Current() (Vertex) {
    // fmt.Printf("i = %d\n", iter.i);
    return (*iter.vertices)[iter.i];
}









// Graph implementation.
type Graph struct {
    adjList map[Vertex] *vector.Vector;
    directed bool;
    
    
    edges *vector.Vector;
}


func (g *Graph) Vertices() VertexIterator {
    vertices := make([]Vertex, len(g.adjList));
    i := 0;
    for v,_ := range g.adjList {
        vertices[i] = v;
        i++;
    }
    return &VertexIter{ &vertices, -1 };
}

func (g *Graph) NumVertices() int {
    return len(g.adjList);
}


func (g *Graph) Reverse() (*Graph) {
    if !g.Directed() {
        fmt.Printf("Reverse(): It does not make sense because graph is undirected.");
    }
    revGraph := NewGraph(g.Directed());
    for _,edges := range g.adjList {
        for i := 0; i < edges.Len(); i++ {
            e := edges.At(i).(*Edge);
            revGraph.AddEdgeWithWeight(e.Dest(), e.Source(), e.Weight());
        }
    }
    return revGraph;
}




func (g *Graph) OutEdges(n Vertex)  EdgeIterator {
    return &EdgeIter{g.adjList[n], -1}; 
}


func (g *Graph) Directed() bool {
    return g.directed;
}

func (g *Graph) HasVertex(v Vertex) bool {
    _,contains := g.adjList[v];
    return contains;
}



/** Returns edges of undirected graph */
func (g *Graph) UndirectedEdges() EdgeIterator {
    if g.edges != nil {
        return &EdgeIter{g.edges, -1};
    }
    m := make(map[Vertex] bool);
    allEdges := vector.New(0);
    for v, edges := range g.adjList {
        m[v] = true;
        for i := 0; i < edges.Len(); i++ {
            edge := edges.At(i).(*Edge);
            allEdges.Push(edge);
            
            if g.directed {
                allEdges.Push(edge);
            } else {
                _,present := m[edge.Dest()];
                if !present {
                    allEdges.Push(edge);
                }
            }
        }
    }
    return &EdgeIter{allEdges, -1};
}

/* Returns all edges in the graph. If the graph is undirected, each edge will
appear twise, but with source and destination switched around. 
*/
func (g *Graph) Edges() EdgeIterator {
    if g.edges != nil {
        return &EdgeIter{g.edges, -1};
    }
    m := make(map[Vertex] bool);
    allEdges := vector.New(0);
    for v, edges := range g.adjList {
        m[v] = true;
        for i := 0; i < edges.Len(); i++ {
            edge := edges.At(i).(*Edge);
            allEdges.Push(edge);
        }
    }
    return &EdgeIter{allEdges, -1};
}


func (g *Graph) SortedUndirectedEdges() EdgeIterator {
    if g.edges != nil {
        return &EdgeIter{g.edges, -1};
    }
    m := make(map[Vertex] bool);
    allEdges := vector.New(0);
    for v, edges := range g.adjList {
        m[v] = true;
        for i := 0; i < edges.Len(); i++ {
            edge := edges.At(i).(*Edge);
            allEdges.Push(edge);
            
            if g.directed {
                allEdges.Push(edge);
            } else {
                _,present := m[edge.Dest()];
                if !present {
                    allEdges.Push(edge);
                }
            }
        }
    }
    sort.Sort(allEdges);
    return &EdgeIter{allEdges, -1};
}




func (g *Graph) AddEdgeWithWeight(from Vertex, to Vertex, weight int64) {
    g.AddNode(from);
    g.AddNode(to);
    edge := Edge {from, to, weight};
    g.adjList[from].Push(&edge);
    if !g.directed {
        edge2 := Edge {to, from, weight};
        g.adjList[to].Push(&edge2);
    }
}


func (g *Graph) AddEdge(from Vertex, to Vertex) {
    g.AddEdgeWithWeight(from, to, 0);
}


func (g *Graph) AddNode(n Vertex) bool {
    _, present := g.adjList[n];
    if present {
        return false;
    }
    g.adjList[n] = vector.New(0);
    return true;
}



func NewGraph(directed bool) *Graph {
    adjList := make(map[Vertex] *vector.Vector);
    return &Graph{adjList, directed, nil};
}


func (g *Graph) String() string {
    var s string = "";
    for node, neighbors := range g.adjList {
        s += fmt.Sprintf("%d", node)       ;
        s += ": ";
        for i := 0; i < neighbors.Len(); i++ {
            var neigh *Edge = neighbors.At(i).(*Edge);
            s += fmt.Sprintf("%d,", neigh.dest);
        }
        s += "\n";
    }
    return s;
}




